package com.algorithm.search;

import java.util.Arrays;
import java.util.Objects;

/**
 * 跳表:不支持null值
 *
 * @program: study
 * @className: SkipTable
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2020-01-14 09:38
 * @version: v1.0
 **/
public class SkipTable {

    /**
     * 跳表的最大层级，默认为16
     */
    private final static int MAX_LEVEL = 16;
    /**
     *  跳表的概率？
     */
    private final static float SKIP_P = 0.5f;
    /**
     * 头指针：不存储数据
     */
    private final Node header = new Node();
    private int level;

    public static void main(String[] args) {
        SkipTable skipTable = new SkipTable();
        for (int i = 0; i < 100; ++i) {
            skipTable.insert(i);
        }
        skipTable.delete(5);
        skipTable.printAll();
    }

    /**
     * 功能描述: 根据值查找val所处的位置
     * <p>
     * 1. 从跳表的最高层级开始查找，直到在该层级找到比目标值大的节点指针；
     * 2. 转向下一层级，继续1
     * 3. 直到第0级，找到或找不到该节点
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/14 10:23 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/14 10:23 上午
     **/
    public Node get(Integer value) {

        Integer val = Objects.requireNonNull(value, "值不能为空");

        Node p = this.header;
        for (int i = level - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.getData() < val) {
                p = p.forwards[i];
            }
        }

        if (p.forwards[0] != null && p.forwards[0].data == val) {
            return p.forwards[0];
        }

        return null;
    }

    /**
     * 功能描述: 插入元素
     * 1. 计算该节点需要在跳表的哪几层进行插入；
     * 2. 构建该节点值
     * 3. 查找各层节点的前驱节点
     * 4. 将该节点插入到每层
     * 5. 更新跳表层高
     *
     * @param value: 插入元素
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/14 10:52 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/14 10:52 上午
     **/
    public void insert(int value) {

        /**
         * level决定了该节点出现在[0, level]的层级上
         */
        int level = this.randomLevel();
        /**
         * 构建节点
         */
        Node node = new Node();
        node.data = value;
        node.maxLevel = level;
        /**
         * 查找各层插入位置
         * 1. 也就是每层中最后一个小于该val的节点指针
         * 2. 保存该指针，用于后续更新
         * 3. 每层的指针，实质上是该新节点指针的前驱节点
         */
        Node[] levelNode = preNodeArray(value, level);
        Node p = header;
        /**
         * 在各层插入该节点
         */
        for (int i = 0; i < level; ++i) {
            /**
             * 新节点的在该层的后继，为其前驱节点在该层的后继节点
             */
            node.forwards[i] = levelNode[i].forwards[i];
            levelNode[i].forwards[i] = node;
        }

        /**
         * 更新节点高度
         */
        if (this.level < level) {
            this.level = level;
        }
    }

    /**
     * 功能描述: 查找指定元素在每层的前驱节点
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/14 11:34 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/14 11:34 上午
     **/
    private final Node[] preNodeArray(int value, int level) {
        Node[] levelNode = new Node[level];
        Arrays.fill(levelNode, this.header);
        Node p = this.header;
        for (int i = level - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            levelNode[i] = p;
        }
        return levelNode;
    }

    /**
     * 功能描述: 删除元素
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/14 11:32 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/14 11:32 上午
     **/
    public void delete(int value) {

        /**
         * 1. 各层元素的前驱节点
         */
        Node[] preNodePreLevelArray = this.preNodeArray(value, this.level);
        /**
         * 2. 获取第0层前向指针
         */
        Node p = preNodePreLevelArray[0];

        /**
         * 3. 如果节点存在则执行删除
         * 此处注意：第0层才是真正的链表
         */
        if (p != null && p.forwards[0].data == value) {
            /**
             * 更新每层指针
             */
            for (int i = this.level - 1; i >= 0; --i) {
                Node current = preNodePreLevelArray[i].forwards[i];
                /**
                 * 判定各层节点是否存在，存在则删除
                 */
                if (current != null && current.data == value) {
                    preNodePreLevelArray[i].forwards[i] = current.forwards[i];
                    current = null;
                }
            }
        }

        /**
         * 4. 更新跳表层级
         * 就是看看跳表的哪一级空了
         */
        while (this.level > 1 && this.header.forwards[this.level] == null) {
            this.level--;
        }


    }

    /**
     * 功能描述: TODO
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/14 11:57 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/14 11:57 上午
     **/
    public final void printAll() {

        Node p = this.header;
        while (p.forwards[0] != null) {
            System.out.print(p.forwards[0].data + " , ");
            p = p.forwards[0];
        }

        System.out.println();
    }

    /**
     * 功能描述: 随机层
     * 1. 随机产生level的层级；
     * 2. 根据阈值决定level的最终数据是多少
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/14 10:53 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/14 10:53 上午
     **/
    private final int randomLevel() {
        int level = 1;
        while (Math.random() < SKIP_P && level < MAX_LEVEL) {
            ++level;
        }
        return level;
    }

    /**
     * 功能描述: 节点
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2020/1/14 10:09 上午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2020/1/14 10:09 上午
     **/

    private final static class Node {
        /**
         * 数据
         */
        private Integer data;
        /**
         * 最大层级
         */
        private int maxLevel;
        /**
         * 前向指针
         */
        private Node[] forwards;

        public Node() {
            this.forwards = new Node[MAX_LEVEL];
        }

        public Integer getData() {
            return data;
        }

        public void setData(Integer data) {
            this.data = data;
        }

        public int getMaxLevel() {
            return maxLevel;
        }

        public void setMaxLevel(int maxLevel) {
            this.maxLevel = maxLevel;
        }

        public Node[] getForwards() {
            return forwards;
        }

        public void setForwards(Node[] forwards) {
            this.forwards = forwards;
        }

    }
}
